1. Technical Field of the Invention
The invention relates to the field of telecommunications and more particularly, to a system and method for providing variable user information rates and for improving performance and bandwidth utilization in telecommunications systems using orthogonal codes for error control.
2. Description of Related Art
The cellular telephone industry has made phenomenal strides in commercial operations throughout the world. Growth in major metropolitan areas has far exceeded expectations and is outstripping system capacity. If this trend continues, the effects of rapid growth will soon reach even the smallest markets. The predominant problem with respect to continued growth is that the customer base is expanding while the amount of electromagnetic spectrum allocated to cellular service providers for use in carrying radio frequency communications remains limited. Innovative solutions are required to meet these increasing capacity needs in the limited available spectrum as well as to maintain high quality service and avoid rising prices.
Currently, channel access is primarily achieved using Frequency Division Multiple Access (FDMA) and Time Division Multiple Access (TDMA) methods. In FDMA systems, a physical communication channel comprises a single radio frequency band into which the transmission power of a signal is concentrated. In TDMA systems, a physical communications channel comprises a time slot in a periodic train of time intervals transmitted over the same radio frequency. Usual methods of implementing a TDMA system incorporate FDMA as well.
Spread spectrum comprises a communications technique that is finding commercial application as a new channel access method in wireless communications. Rudimentary spread spectrum systems have been around since the days of World War II. Early applications were predominantly military-oriented (relating to smart jamming and radar). However, there is an increasing interest today in using spread spectrum systems in communications applications, including digital cellular radio, land mobile radio, and indoor/outdoor personal communication networks.
Spread spectrum operates quite differently from conventional TDMA and FDMA communications systems. In a direct sequence code division multiple access (DS-CDMA) spread spectrum transmitter, for example, a digital symbol stream for a given dedicated or common channel at a basic symbol rate is spread to a xe2x80x9cchipxe2x80x9d rate. This spreading operation involves applying a spreading code that is channel-unique (sometimes referred to as a xe2x80x9csignature sequencexe2x80x9d) to the symbol stream that increases its transmission rate (as well as the bandwidth requirement) while adding redundancy. Typically, the digital symbol stream is multiplied by the unique digital code during spreading. The intermediate signal comprising the resulting data sequences (chips) is then summed with other similarly processed (i.e., spread) intermediate signals relating to other (dedicated or common) channels.
A scrambling code that is unique to a base station (often referred to as a xe2x80x9clong codexe2x80x9d since in most cases it is longer than the spreading code) is then applied to the summed intermediate signals to generate an output signal for multi-channel transmission over a communications medium. The intermediate signals derived from the various dedicated or common channels thus advantageously share one transmission communications frequency band, with the multiple signals appearing to be located on top of each other in both the frequency domain as well as the time domain. Because the applied spreading codes are unique to each channel, however, each intermediate signal that is transmitted over the shared communications frequency is similarly unique, and may be distinguished from others through the application of proper processing techniques at the receiver end.
In the DS-CDMA spread spectrum mobile station (receiver), the received signals are recovered by applying (i.e., multiplying, or matching) the appropriate scrambling and spreading codes to despread, or remove the coding from the desired transmitted signal and return to the basic symbol rate. Where the spreading code is applied to other transmitted and received intermediate signals, however, only noise is produced. The despreading operation thus effectively comprises a correlation process comparing the received signal with the appropriate digital code to recover the desired information from the channel.
Orthogonal codes or near-orthogonal codes (i.e., codes having relative high relative auto-correlation and low relative cross-correlation values) are used for error control in telecommunications systems. Walsh codes are one example of an orthogonal code. In a coding scheme using Walsh codes, a k-bit information word (xe2x80x9cinfowordxe2x80x9d) is converted into a 2k-bit sequence using the Hadamard transform. Such a conversion will be referred to in this patent application as a (2k,k) orthogonal code. A Walsh code for encoding a 2-bit information sequence to a 4-bit orthogonal codeword is shown below:       H    4    =      "LeftBracketingBar"                            1                          1                          1                          1                                                  -            1                                    1                                      -            1                                    1                                      1                          1                                      -            1                                                -            1                                                1                                      -            1                                                -            1                                    1                      "RightBracketingBar"  
Here, the four rows of the matrix H4 form the code words for the four information symbol sequences whose binary values are equal to the numeric values of the four row indices. For example, the information sequences (0,0), (0,1), (1,0) and (1,1) would be mapped to the codewords (1,1,1,1), (1,xe2x88x921,1,xe2x88x921), (1,1,xe2x88x921,xe2x88x921) and (1,xe2x88x921,xe2x88x921,1) respectively. The Fast Hadamard Transform is then used to demodulate the incoming signal non-coherently. The Fast Hadamard Transform acts as a correlator, and those code-word(s) (or component(s) thereof) that have the highest correlation values can then be identified as the transmitted code-word(s). The uniqueness of the mapping between the 2-bit information sequences and the 4-symbol code words (in the example above) allows the unambiguous detection and decoding of the transmitted symbols.
The use of the Walsh-Hadamard codes described above result in a bandwidth expansion of 2k/k (i.e., a k-bit information word expands to a 2k-bit code word) which is quite high. The inverse of the bandwidth expansion is referred to as the coding rate. Consequently, these Walsh-Hadamard codes are normally used in very low signal-to-noise ratio environments. For example, the IS-95 CDMA system compensates the low signal-to-interference ratios in the system through the use of such codes. Another application for such schemes is in random access protocols for cellular and mobile satellite systems, where users may be trying to initially synchronize to the system, or attempting to originate a call or answer an incoming call.
It has been found desirable to find new techniques to improve the coding rate in a telecommunications system employing orthogonal codes. It has further been found desirable to find techniques for reducing the bandwidth expansion. An ideal telecommunications system employing orthogonal codes would thus have only that bandwidth expansion that is necessary to separate the multiple transmissions from various users without reducing the efficiency of spectrum utilization by too large a factor.
It is therefore a primary object of the present invention to provide improved performance in telecommunications systems using orthogonal codes for error control. It is a further object of the present invention to reduce bandwidth expansion in such telecommunications systems. It is also an object of the present invention to improve the coding rate in a telecommunications system employing orthogonal codes.
Orthogonal codes or near-orthogonal codes (i.e., codes having high relative auto-correlation and low relative cross-correlation values) are used for error control in communication systems. For example, the IS-95 CDMA cellular standard uses a (64,6) orthogonal Walsh code on the reverse link (i.e., the link from the mobile station to the base station) for error control. As noted earlier, such a set of Walsh codes converts each 6-bit information word into a 64-symbol code word in such a way that each of the sixty-four such 64-symbol codes are orthogonal relative to each other.
The present invention allows variable transmission rates and/or improved error performance to be provided to users in conjunction with the use of orthogonal or near-orthogonal codes. In one embodiment of the present invention, this is achieved by the parallel (i.e., simultaneous) transmission of multiple codewords each of which represents a different information sequence. In an alternative embodiment, multiple shorter orthogonal codewords with higher coding rates are transmitted sequentially (one after the other) such that their combined length is the same as the original codeword. In an extension of the present invention, these two methods are combined to transmit sets of shorter codewords both simultaneously and sequentially.
When multiple codewords are transmitted simultaneously, the associated decoder needs to be able to determine the relative sequence of the codewords being transmitted simultaneously. In the preferred embodiment of the present invention, part of the information sequence being encoded is used for this purpose. The receiver decodes the transmitted codewords by selecting those codewords that have the highest correlation values with the received sequence.
It should be noted that orthogonal or near-orthogonal codes are used in some concatenated coding schemes. For example, the IS-95 CDMA standard specifies a concatenated coding scheme where a convolutional code having a rate of 1/3 and a constraint length of 9 is followed by a repetition code and a (64,6) Walsh code. In this IS-95 standard, the convolutional code is called the outer code while the Walsh code is called the inner code. In a system with concatenated coding where orthogonal or near-orthogonal codes are used as the inner code, the transmission of multiple codewords (both simultaneously and sequentially) can be used to increase the redundancy of the outer code and possibly improve the error performance of the overall coding scheme while maintaining the same overall bandwidth expansion. In this manner, the system and method of the present invention can be used to provide variable transmission rates and possibly improve error performance for a system using concatenated coding.
The present invention aims at allowing variable information rates or improved error performance with orthogonal or near-orthogonal coding through better bandwidth utilization. This is achieved by simultaneously transmitting two or more code words from a given orthogonal code set and/or by transmitting multiple shorter orthogonal codewords sequentially such that their combined length equals the longer codeword. It should be emphasized that the present invention can be used with any orthogonal or near-orthogonal code set.
The system and method of the present invention may be used in a variety of applications, e.g., in wireless communication systems, cellular radio, satellite communications, simulcast transmission, land mobile radio and cellular systems, etc. The use of the techniques detailed in the present application permits an increase in the information rate without a concomitant increase in the bandwidth requirement. This increased information rate can be used to provide variable information rates to users.
In one aspect the present invention is a system and method for improving the coding efficiency and bandwidth utilization of a Code Division Multiple Access (CDMA) transmission channel. The technique of the present invention permits the efficient encoding and transmission of an original information word having 2k bits by splitting the original information word into two equal parts having k bits each.
One part of the original information word is extended with a single bit having the value zero. The other part of the original information word is extended with a single bit having the value one. The extension of the halfwords can be done by prefixing or suffixing the additional bit to the halfword or by inserting the additional bit into the halfword.
The k+1 bits of the two extended halfwords are then encoded using a (2k+1,k+1) Walsh code to obtain two corresponding Walsh codewords, each having 2k+1 symbols. The two Walsh codewords are summed to obtain a composite Walsh codeword having 2k+1 symbols. The composite Walsh codeword having 2k+1 symbols is then optionally modulated and transmitted over an air interface. If the composite Walsh codeword having 2k+1 symbols is modulated and transmitted over an air interface, in another aspect of the present invention this transmission is received over an air interface and demodulated to recover the pair of composite Walsh codeword each having 2k+1 symbols.
In another aspect, the system and method of the present invention also presents a technique for decoding a demodulated composite Walsh codeword received over a Code Division Multiple Access (CDMA) transmission channel. In this aspect, a received composite Walsh codeword is first decomposed into its component Walsh codewords using the Fast Hadamard Transform. Each of the component Walsh codewords is then decoded to obtain associated information halfwords.
The decoded information halfwords are sorted into two lists based upon the value of an index bit at a specific position in the halfword being either zero or one. The decoded information halfwords are then further sorted in decreasing order of correlation between the Walsh codeword associated with the halfword and the composite Walsh codeword received. The index bit is then deleted from the two information halfwords having the highest correlation values to obtain two corresponding data halfwords. The two data halfwords are then concatenated in a specific order to recover the original information word that was transmitted.
In another aspect, the system and method of the present invention can be generalized to the simultaneous transmission of multiple encoded information partwords. In this aspect, an original information word having M times K bits of binary information is split into M information partwords having K bits each. Each of the M information partwords is concatenated or combined with N index bits, where N is at least equal to ┌log2 M┐.
In the preferred embodiment of the present invention, the index bits for the mth information partword are the binary representation of mxe2x88x921. As before, the N index bits can be prefixed, suffixed or intermixed with the K bits of the information partword. The K+N bits of the M extended information partwords are then encoded using a (2K+N, K+N) Walsh code to obtain a group of M Walsh codewords, each having 2K+N symbols. The M Walsh codewords are then summed to obtain a summed Walsh codeword with 2K+N symbols that is optionally modulated and transmitted over a broadcast channel.
The associated decoder of the present invention first demodulates a composite Walsh codeword received over a Code Division Multiple Access (CDMA) transmission channel. The received composite Walsh codeword of length 2K+N symbols is next decomposed into M lists of component Walsh codewords having 2K+N symbols each using the Fast Hadamard Transform. Each of the M lists of component Walsh codewords is then decoded to obtain M lists of information partwords each of which is K+N bits in length.
The components of the M lists of decoded information partwords are chosen based upon the binary value contained in the N index bits of the partwords. Each of the M lists of decoded information partwords is sorted by decreasing value of correlation between the Walsh codeword associated with a partword and the received composite Walsh codeword.
The highest ranking partword is next selected from each of the M lists and these M selected partwords are then converted into M data partwords of K bits each by deleting the N index bits from each of the partwords. Finally, the M data partwords are assembled in a specific order using the index bits to recover the original information word.
In a further embodiment of the present invention, an original information word having M times K bits of binary information is split into M information partwords having, on average, K bits each (i.e., Mxc2x7K=k1+k2+ . . . +km). Each of the M information partwords is combined with N index bits, where N is at least equal to ┌log2 M┐. The rest of the coding and decoding process for this embodiment of the invention is the same as for the earlier case where the M information partwords were of equal length.
In yet another aspect, the present invention discloses a system and method for encoding an original information word having └log2 (22kxe2x88x921+2Kxe2x88x921)┘ bits of binary information. In this aspect, a set of extended Walsh codes 2K symbols in length is created first. The extended Walsh code set includes all single Walsh codewords having 2K symbols and all combinations of two 2K-symbol Walsh codewords.
Each distinct information word is mapped to either a simple codeword or to a combination of two codewords from the extended Walsh code set. If the information codeword is mapped to a simple Walsh codeword, the simple codeword is modulated and transmitted. If the information codeword is mapped to a combination of two Walsh codewords, the two Walsh codewords are summed, modulated and transmitted in parallel. All transmitted codewords are buffered as appropriate to obtain a uniformly framed Walsh codeword 2K symbols in length.
The associated decoder of the present invention first demodulates the composite Walsh codeword received over a telecommunications channel employing orthogonal codes. A threshold value is first specified that sets the maximum acceptable difference in the correlation values of received Walsh codeword pairs.
The received composite codeword of length 2k symbols is decomposed into one or more component Walsh codewords having 2K symbols each using the Fast Hadamard Transform. The component Walsh codewords are sorted in decreasing order of correlation between the component codewords and the composite Walsh codeword.
The two highest ranking component codewords are selected from the list if the difference between their correlation values is less than the specified threshold value. On the other hand, if the difference between the correlation values of the two highest ranking component codewords is more than the specified threshold value, then only the highest ranking component Walsh codewords is selected for decoding. Finally, a mapping table is used to look up the information word that is associated with the selected Walsh codeword(s).
In another aspect of the present invention, an information word having 2K bits is serially encoded by splitting the information word into a first part having K+M bits and a second part having Kxe2x88x92M bits. The K+M bits of the first part of the information word are encoded using a (2K+M,K+M) Walsh code to obtain a first Walsh codeword having 2K+M symbols. The Kxe2x88x92M bits of the second part of the information word are encoded using a (2Kxe2x88x92M,Kxe2x88x92M) Walsh code to obtain a second Walsh codeword having 2Kxe2x88x92M symbols. The two Walsh codewords are then concatenated to obtain an extended Walsh codeword with 2K+M+2Kxe2x88x92M symbols. This extended Walsh codeword is then modulated and transmitted over an air interface.
The decoder associated with the above encoding scheme first demodulates the composite Walsh codeword received over a telecommunications channel employing orthogonal codes to yield a concatenated Walsh codeword that comprises two sequentially transmitted Walsh codewordsxe2x80x94one 2K+M symbols in length and the other 2Kxe2x88x92M symbols in length. This received Walsh codeword frame is first split into its pair of component Walsh codewords (of length 2k+M and 2kxe2x88x92M symbols).
The pair of component Walsh codewords are next translated into a pair of information partwords having K+M bit and a Kxe2x88x92M bit using the Fast Hadamard Transform. The pair of translated information partwords are then reassembled in a prespecified order (such as in the order in which they were received) to recover the original information word having 2K bits.
In a further embodiment of the present invention, an original information word having M times K bits of binary information is split into M information partwords having, on average, K bits each (i.e., Mxc2x7K=k1+k2+ . . . +km). Each of the M information partwords is combined with N index bits, where N is at least equal to ┌log2 M┐. These M extended (and possibly unequal) partwords are then sequentially transmitted as M Walsh codewordsxe2x80x94of length 2k, 2k2, . . . 2km symbols. The rest of the coding and decoding process for this embodiment of the invention is similar to the case where the sequentially transmitted partitions are equal in length.
A simplified decoder associated with the same encoding scheme first demodulates the composite Walsh codeword received over a telecommunications channel employing orthogonal codes to yield a concatenated Walsh codeword that comprises M sequentially transmitted Walsh codewords each 2K symbols in length. This received Walsh codeword frame is first split into M component Walsh codewords each having 2K symbols.
Each of the M component Walsh codewords are then translated into a K-bit information partword using a mapping table. Each of the M translated information partwords are then reassembled in the order in which they were received to recover the original information word having K times M bits.